#ifndef __DIJKSTRA__
#define __DIJKSTRA__


#include <iostream>
#include <vector>
#include <queue>

#include "meta_search.hpp"

namespace graph_search{
    struct Node{
        int x;
        int y;
        int dist;
        Node(int x,int y,int dist):x(x),y(y),dist(dist){}
        bool operator<(const Node& rhs) const{
            return dist > rhs.dist;
        }
    };
    class dijkstra:public search{
        private:
            const int INF = 1e7;
            bool isValid(int x,int y,int n){
                return x>=0 && y>=0 && x<n && y<n;
            }
        public:
            int find(const std::vector<std::vector<int>>& matrix,Position start,Position end){
                int n = matrix.size();
                std::vector<std::vector<int>> dist(n,std::vector<int>(n,INF));
                std::priority_queue<Node> pq;
                pq.push(Node(start.x,start.y,matrix[start.x][start.y]));
                dist[start.x][start.y] = matrix[start.x][start.y];

                while(!pq.empty()){
                    Node current = pq.top();
                    pq.pop();

                    if(current.x == end.x && current.y == end.y){
                        return current.dist;
                    }

                    for(int i=0;i<4;i++){
                        int x = current.x + dx[i];
                        int y = current.y + dy[i];

                        if(isValid(x,y,n) && current.dist + matrix[x][y] < dist[x][y]){
                            dist[x][y] = current.dist + matrix[x][y];
                            pq.push(Node(x,y,dist[x][y]));
                        }
                    }
                }
                return -1;
            }
    };
}

#endif